The disclosed invention relates to the equalization of a received signal at a wireless receiver in a wireless communication system. More specifically, the disclosed invention relates to an optimized implementation of a Viterbi equalizer for estimating a Minimum Shift Keying (MSK) modulated signal.
In wireless communication, the transmission channel introduces Inter Symbol Interference (ISI) in the received signal. An equalizer is used at the wireless receiver to estimate the transmitted signal in the presence of ISI. A method of equalization, known as maximum likelihood sequence estimation (MLSE), determines the sequence of symbols that is most likely to have been transmitted by the transmitter. MLSE is commonly used in wireless receivers such as Gaussian Minimum Shift Keying (GMSK) receivers used in the Global System for Mobile communication (GSM) systems. MLSE equalizers use an algorithm known as the Viterbi algorithm to estimate the maximum likelihood sequence.
The Viterbi algorithm estimates the maximum likelihood transmitted signal at the wireless receiver, using the prior knowledge of the received signal, the channel impulse response, and the possible values of transmitted symbols. In order to use the knowledge of the possible values of the transmitted symbols, the MLSE equalizer is implemented as a state machine. The possible states of the equalizer are based on the possible values of the previous L transmitted symbols, where L is the length of the inter symbol interference introduced in the channel. Further, the state transition of the equalizer at a stage is decided by using the channel impulse response and the symbol received at that stage. To efficiently use the information available with the wireless receiver, the Viterbi algorithm uses a Viterbi trellis to represent the states and state transitions of the equalizer. The maximum likelihood sequence of the transmitted symbols is estimated by traversing the Viterbi trellis and determining a set of maximum likelihood state transitions at each stage.
Referring now primarily to FIG. 1, the Viterbi trellis for stages n and n+1 is hereinafter described. A set 102 of the previous L transmitted symbols define the Viterbi state at stage n. Similarly, a set 104 of the previous L transmitted symbols define the Viterbi state at stage n+1. Assuming two possible values {p1, p2} of the transmitted symbol, 2L Viterbi states are possible at a stage. These Viterbi states are shown as {S1, S2, . . . , S2L}. Further, a Viterbi state set S={S1, S2, . . . , S2L} comprises all possible Viterbi states at a stage. A possible state transition is hereinafter referred to as a branch. In a Viterbi trellis, two branches originate from each Viterbi state at a stage. Each of these branches corresponds to a possible value of the transmitted symbol. For example, branches 106 and 110, originating from Viterbi state S1 at stage n, correspond to the transmitted symbols p1 and p2 respectively. Further, two branches lead to each state at a stage. For example, branches 106 and 108 lead to Viterbi state S1 at stage n+1. A series of branches (state transitions) is hereinafter referred to as a path.
The Viterbi algorithm uses the Viterbi trellis to estimate the most likely sequence of transmitted symbols. The Viterbi algorithm involves performing a set of steps for each stage, hereinafter referred to as advancing the Viterbi trellis by a stage. The steps involve determining one surviving path leading to each Viterbi state at the stage and taking a decision regarding a symbol at a finite number of stages N preceding the current stage. After the Viterbi trellis has been advanced by a stage, only one path for each Viterbi state at the stage survives. Therefore, only two possible paths leading to each Viterbi state at the subsequent stage remain. For example, paths 112 and 114 survive for Viterbi states S1 and S2 at stage n−1. Correspondingly, two paths leading to Viterbi state S1 remain at stage n. Once the surviving paths are determined at stage n, a decision is taken regarding a symbol at a finite number of stages N preceding stage n. The method of determining surviving paths and taking the decision is repeated at each stage of the Viterbi trellis to estimate a maximum likelihood sequence of symbols. The method of determining surviving paths is described with reference to FIG. 2. Further, the method of estimating the maximum likelihood sequence of symbols is described with reference to FIG. 3.
Referring now primarily to FIG. 2, the method of determining surviving paths for stage n, is hereinafter described. At step 202, the received signal is convolved with the conjugate of the time-inverted channel to obtain a symbol yn representing the received symbol at stage n. Thereafter, the first Viterbi state from Viterbi state set S is considered as state Sk at step 204. Two possible paths lead to Viterbi state Sk at a stage n+1. At step 206, a path metric for the first possible path, leading to Viterbi state Sk at stage n+1, is obtained using the relation
                                          CM            n                    ⁡                      (                                          I                n                            ,                              S                k                                      )                          =                                            CM                              n                -                1                                      ⁡                          (                                                I                                      n                    -                    1                                                  ,                                  S                                      k                    ′                                                              )                                +                      2            ⁢            ℛ            ⁢                          {                                                I                  n                                *                                  y                  n                                            }                                -                      2            ⁢            ℛ            ⁢                          {                                                I                  n                                *                                                      ∑                                          m                      =                      1                                        L                                    ⁢                                                            I                                              n                        -                        m                                                              *                                          x                      m                                                                                  }                                -                                                                                      I                  n                                                            2                        ⁢                          x              0                                                          (        1        )            where In denotes the transmitted symbol at stage n, Sk′ is the Viterbi state on the first possible path at stage n, CMn(In,Sk) is the path metric of a possible path leading to Viterbi state Sk at stage n+1, as obtained at stage n, CMn−1(In−1,Sk′) is the path metric of the surviving path leading to stage Sk′ at stage n, as obtained at stage n−1, set {In−m,m∈[1,L],m∈I} correspond to Viterbi state Sk, and xm is the autocorrelation value of the channel impulse response for the time delay of m stages. At step 208, the path metric for the second possible path is similarly obtained. At step 210, the path with a higher path metric among the above two paths is selected as the surviving path for Viterbi state Sk at stage n+1. At step 212, it is checked whether Viterbi state Sk is the last state of Viterbi state set S. If the Viterbi state Sk is not found to be the last Viterbi state, then the next state from Viterbi state set S is considered as state Sk at step 214. Steps 206, 208 and 210 are then repeated for the new state Sk. Therefore, the surviving paths leading to all the states of Viterbi state set S is determined at stage n.
Referring now primarily to FIG. 3, the method of estimating the maximum likelihood sequence of symbols, is hereinafter described. The stage of the Viterbi trellis corresponding to the first symbol to be equalized is considered as stage n, at step 302. At step 304, the Viterbi trellis is then advanced by stage n, in accordance with the method described with reference to FIG. 2. Therefore, step 304 obtains 2L surviving paths, each corresponding to a Viterbi state. Thereafter, the path with the highest path metric is selected from these surviving paths as a maximum likelihood (ML) path at stage n at step 306. At step 308, a trace back along the ML path by a finite number of stages N is performed. A series of branches at multiple stages constitute a path. In addition, a branch at a stage corresponds to a state transition, which, in turn, corresponds to a symbol at that stage. Therefore, a path corresponds to a series of symbols. Therefore, step 308 of tracing back determines the symbols at previous stages along the ML path. At step 310, the symbol determined at stage n−N by tracing back is established as the symbol transmitted at stage n−N. At step 312, it is verified whether stage n is the last stage to be equalized. If stage n is not found to be the last stage to be equalized, then the next stage is considered to be stage n at step 314. Steps 304 to 310 are then repeated for the new stage n. Therefore, a sequence of transmitted symbols is estimated by the above method.
An implementation of an MLSE equalizer is disclosed in EPO Patent Application No. EP01246418A2, publication date Oct. 2, 2002, titled “Hybrid Equalizer With Feedback And Sequence Estimation”, to Broadcom Corporation. The disclosed implementation combines the benefits of a decision feedback equalizer (DFE) with a maximum-a-posterori (MAP) equalizer (or a maximum likelihood sequence estimator, MLSE) to perform equalization in a time-forward or time-reversed manner. The selection of the time-forward or time-reversed manner is based on the channel being minimum phase or maximum phase. The disclosed equalization device has lower complexity than a full-state MAP device.
Another equalizer, which exploits the alternate real and imaginary nature of the received signal, is disclosed in U.S. Pat. No. 5,905,757, publication date May 18, 1999, titled “Filter Co-processor”, to Motorola, Inc. The patent discloses a filter co-processor within a Digital Signal Processor (DSP) that takes advantage of the orthogonal nature of the modulated signals during the equalization process. Since after reception, only certain real/imaginary values of the received signal are useful for demodulation, the filter co-processor only processes those values to estimate the transmitted signal. By processing only those values useful for demodulation, the filter co-processor is able to process more information in a given amount of time, leading to increased processing when compared to the prior art.
Both the aforementioned equalizers exploit certain redundancies in MLSE equalization to reduce the complexity of the equalization process. However, both the above implementations exploit only some of the redundancies inherently present in the MLSE equalization. There are many redundancies in the MLSE equalization computation that these implementations fail to exploit. Further, most mobile receivers, such as MSK receivers, have limited processing power and memory resources. Therefore, there is a need for a more efficient implementation of an MLSE equalizer that exploits all the redundancies inherent in the computations of the MLSE equalization.